This invention relates to a technology of managing a database that can be searched with the use of an index.
The amount of information handled by embedded devices, as exemplified by vehicle navigation systems and cellular phones, is increasing on a daily basis. End-users of embedded devices wish to use the ever increasing information at any time without experiencing inconveniences. On the other hand, from the standpoint of the usability of embedded devices, end-users prefer the overall sizes of embedded devices to be as small as possible.
It is extremely difficult to keep fulfilling end-users' demands if manufacturers develop embedded devices by developing data processing modules from scratch on their own. For that reason, as many enterprise systems implement data processing with the use of a database management system (DBMS), embedded devices, too, are beginning to utilize DBMS as a data management platform in order to assume data manipulation functions easily and quickly.
In order to facilitate the securing of more programmers for the development of an application program that is run on an embedded device to provide various functions to end-users, it is desirable to employ a data model that is in the two-dimensional table format and data manipulation requests that are in SQL. In the two-dimensional table format, one piece of data contains a plurality of data fields (attributes) which constitute “columns”, and constitutes a “row”. A plurality of “rows” together constitute a “table”. The query language that is used to manipulate data held in the “table” is SQL.
From the standpoint of the usability of embedded devices, specifically the ease of handling (compactness), the major two requirements that a DBMS used in an embedded device is expected to meet are as follows.
1. Implementing data manipulation functions including the data search function quickly while keeping the footprint small (i.e., keeping the CPU utilization ratio low).
2. Storing as large an amount of data as possible in a storage area that is installed in the embedded device.
Embedded devices are also required to provide end-users with data manipulation services for manipulating data from a diversity of perspectives. For example, many of recent vehicle navigation systems instruct end-users to specify a destination by inputting keywords from a plurality of aspects such as the address, the phone number, the name of the institution, and the type (genre) of the institution in order to search for the destination.
Various technologies have been disclosed as efficient ways to conduct a full-text search for specified keywords on a database. For example, JP 2007-299021 A discloses a full-text search technology that keeps an index for full-text search separately from the body of input and stored data. This full-text search technology includes a technology in which, upon reception of a search request, the index for full-text search is used to quickly identify data that meets a criterion of a keyword specified by an end-user. The data body here is implemented as a row in the table format data model described above. For database construction technology including a concrete data structure that implements a row, see, for instance, Jim Gray and Andreas Reuter, “Transaction Processing: Concepts and Techniques”, Morgan Kaufmann Publishers, 1993, p. 772-784.